<?php
/**
 * @title 200. 岛屿数量 - 减少if判断
 * @author start2004
 */

// ini_set("memory_limit", "128M");


class Solution {

    /**
     * @param String[][] $grid
     * @return Integer
     */
    function numIslands($grid) {
        /**
         * @since 2020-08-13 宽高
         */
        $h = count($grid);
        if($h == 0){
            return 0;
        } else {}
        $w = count($grid[0]);

        /**
         * @since 2020-08-13 外围增加一圈水
         * @since 2020-08-13 上下各一层
         */
        $arr = array_fill(0, $w, "0");
        $grid[-1] = $arr;
        $grid[$h] = $arr;

        /**
         * @since 2020-08-13 左右一层
         */
        for($i=-1; $i<=$h; $i++){
            $grid[$i][-1] = "0";
            $grid[$i][$w] = "0";
        }

        /**
         * @since 2020-08-13 岛屿数量
         */
        $result = 0;

        /**
         * @since 2020-08-13 扫`1`
         */
        for($i=0; $i<$h; $i++){
            for ($j=0; $j<$w; $j++){
                $n = $grid[$i][$j];

                /**
                 * @since 2020-08-13 发现陆地
                 */
                if($n == "1"){
                    $result++;

                    /**
                     * @since 2020-08-13 4个方向扩散
                     */
                    $k = $i ."-". $j;
                    $nexts = [$k=>[$i, $j]];
                    while($nexts){
                        $nextsTmp = [];

                        /**
                         * @since 2020-08-13 遍历
                         */
                        foreach ($nexts as list($n, $m)){
                            if($grid[$n][$m] == "1"){
                                /**
                                 * @since 2020-08-13 防止反复
                                 */
                                $grid[$n][$m] = "0";

                                /**
                                 * @since 2020-08-13 向上
                                 */
                                $nextsTmp[($n-1) ."-". $m] = [$n-1, $m];

                                /**
                                 * @since 2020-08-13 向下
                                 */
                                $nextsTmp[($n+1) ."-". $m] = [$n+1, $m];

                                /**
                                 * @since 2020-08-13 向左
                                 */
                                $nextsTmp[$n ."-". ($m-1)]  = [$n, $m-1];

                                /**
                                 * @since 2020-08-13 向右
                                 */
                                $nextsTmp[$n ."-". ($m+1)] = [$n, $m+1];
                            } else {}
                        }

                        /**
                         * @since 2020-08-13 下次递归
                         */
                        $nexts = $nextsTmp;
                    }
                } else {}
            }
        }

        /**
         * @return
         */
        return $result;
    }
}


/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.13_4.php
 */
$datas = [
    // [
    //     ['1','1','1','1','0'],
    //     ['1','1','0','1','0'],
    //     ['1','1','0','0','0'],
    //     ['0','0','0','0','0']
    // ],
    //
    // [
    //     ['1','1','0','0','0'],
    //     ['1','1','0','0','0'],
    //     ['0','0','1','0','0'],
    //     ['0','0','0','1','1']
    // ],

    [["1","1","1","1","1","0","1","1","1","1","1","1","1","1","1","0","1","0","1","1"],["0","1","1","1","1","1","1","1","1","1","1","1","1","0","1","1","1","1","1","0"],["1","0","1","1","1","0","0","1","1","0","1","1","1","1","1","1","1","1","1","1"],["1","1","1","1","0","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],["1","0","0","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],["1","0","1","1","1","1","1","1","0","1","1","1","0","1","1","1","0","1","1","1"],["0","1","1","1","1","1","1","1","1","1","1","1","0","1","1","0","1","1","1","1"],["1","1","1","1","1","1","1","1","1","1","1","1","0","1","1","1","1","0","1","1"],["1","1","1","1","1","1","1","1","1","1","0","1","1","1","1","1","1","1","1","1"],["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],["0","1","1","1","1","1","1","1","0","1","1","1","1","1","1","1","1","1","1","1"],["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],["1","1","1","1","1","0","1","1","1","1","1","1","1","0","1","1","1","1","1","1"],["1","0","1","1","1","1","1","0","1","1","1","0","1","1","1","1","0","1","1","1"],["1","1","1","1","1","1","1","1","1","1","1","1","0","1","1","1","1","1","1","0"],["1","1","1","1","1","1","1","1","1","1","1","1","1","0","1","1","1","1","0","0"],["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"]],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof(2);
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->numIslands($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
